//假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。 
//
// 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 
//costs 来表示的。 
//
// 例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。 
//
// 请计算出粉刷完所有房子最少的花费成本。 
//
// 
//
// 示例 1： 
//
// 
//输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
//输出: 10
//解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
//     最少花费: 2 + 5 + 3 = 10。
// 
//
// 示例 2： 
//
// 
//输入: costs = [[7,6,2]]
//输出: 2
// 
//
// 
//
// 提示: 
//
// 
// costs.length == n 
// costs[i].length == 3 
// 1 <= n <= 100 
// 1 <= costs[i][j] <= 20 
// 
//
// 
//
// 
// 注意：本题与主站 256 题相同：https://leetcode-cn.com/problems/paint-house/ 
//
// Related Topics 数组 动态规划 👍 133 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class SolutionOffer2_091 {
    /**
     * 可用滚动数组优化空间复杂度
     * @param costs
     * @return
     */
    public int minCost(int[][] costs) {
        int length = costs.length;
        //dp[i][j]:第i个房子刷成第j个颜色后，前i个房子的总成本的最小值
        int[][] dp = new int[length +1][4];
        for(int i = 0; i < dp.length; i++){
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        for(int i = 1; i <= length; i++){
            for(int j = 1; j <= 3; j++){
                if(i == 1) {   //第一行初始化
                    dp[i][j] = costs[i-1][j-1];
                    continue;
                }
                for(int k = 1; k <= 3; k++){
                    if(k == j){ //相邻的房子颜色不能相同
                        continue;
                    }
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][k]+costs[i-1][j-1]);
                }
            }
        }
        //用steam流代替
//        int result = Integer.MAX_VALUE;
//        for(int i : dp[length]){
//            result = Math.min(result, i);
//        }
        return Arrays.stream(dp[length]).min().getAsInt();
    }

    public static void main(String[] args) {
        new SolutionOffer2_091().minCost(new int[][]{{17,2,17},{16,16,5},{14,3,19}});
    }
}
//leetcode submit region end(Prohibit modification and deletion)
